package com.yangli.leecode.b;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @author ly
 * @description
 * @data 2022/4/29
 */
public class FourSum {
    public static void main(String[] args) {
        FourSum fourSum = new FourSum();
        System.out.println(fourSum.fourSum(new int[]{-2, -1, -1, 1, 1, 2, 2}, 0));
    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        int length = nums.length;
        if (length < 4) {
            return Collections.emptyList();
        }
        Arrays.sort(nums);
        List<List<Integer>> res = new LinkedList<>();
        for (int i = 0; i < length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {//第一个位置重复的进行计算了
                continue;
            }
            for (int j = i + 1; j < length; j++) {
                if (j - 1 > i && nums[j] == nums[j - 1]) {//第一个位置重复的进行计算了 j-1>i 表示j的前一个一定是在i的范围之内
                    continue;
                }
                int start = j + 1, end = length - 1;
                while (start < end) {
                    int threeSum = nums[i] + nums[j] + nums[start] + nums[end];
                    if (threeSum > target) {
                        end--;
                    } else if (threeSum < target) {
                        start++;
                    } else {
                        List<Integer> temp = List.of(nums[i], nums[j], nums[start], nums[end]);
                        res.add(temp);
                        //相等的时候，左右各减
                        if (nums[start] == nums[end]) {
                            break;
                        }
                        //相等的时候，要判断下一个节点是否相等，否则就重复了
                        while (start < end && nums[start] == nums[start + 1]) {
                            start++;
                        }
                        while (start < end && nums[end] == nums[end - 1]) {
                            end--;
                        }
                        start++;
                        end--;
                    }
                }
            }
        }
        return res;
    }

}
